package com.lims.algorithm.algset.graph;

import com.sun.media.sound.SoftTuning;
import org.apache.commons.lang3.StringUtils;

import java.lang.reflect.Array;
import java.nio.file.Path;
import java.security.DigestException;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.stream.Stream;

/**
 * <描述:>
 *
 * @author lims
 * @date 2020-09-05 00:47
 */
public class DGraphMatrix {
    /**
     * 最大值
     */
    private static final int INF = Integer.MAX_VALUE;
    /**
     * 顶点集合
     */
    private String[] vertexs;
    /**
     * 边矩阵
     */
    private int[][] edges;
    /**
     * 访问标记
     */
    private boolean[] isVisited;
    /**
     * 最大顶点数
     */
    private int verMaxNum;
    /**
     * 实际顶点数
     */
    private int verNum;

    public DGraphMatrix(int n) {
        vertexs = new String[n];
        edges = new int[n][n];
        isVisited = new boolean[n];
        verMaxNum = n;
        verNum = 0;
    }

    public void addVer(String ver) {
        vertexs[verNum++] = ver;
    }

    public void addEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
    }

    public String getValue(int index) {
        return vertexs[index];
    }

    /**
     * 返回v1，v2权重
     */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    public void show() {
        System.out.println("图邻接矩阵显示：");
        for (int[] edge : edges) {
            for (int i : edge) {
                System.out.printf("%3d", i);
            }
            System.out.printf("\n");
        }
        System.out.printf("\n");
    }

    /**
     * 拿到第一个邻接点的下标
     */
    public int getFirstAjc(int ver) {
        for (int i = 0; i < vertexs.length; ++i) {
            if (edges[ver][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 拿到v1的邻接点下标，除了v2
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getNextAjc(int v1, int v2) {
        for (int i = v2 + 1; i < vertexs.length; ++i) {
            if (edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * v1下一个未被访问过的邻接点
     */
    public int getNextNoAccessAjcVer(int v1) {
        for (int j = 0; j < vertexs.length; j++) {
            // 存在边
            if (edges[v1][j] > 0 && !isVisited[j]) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 清空访问记录
     */
    public void clearVisited() {
        isVisited = new boolean[vertexs.length];
    }

    public void DFS() {
        System.out.println("深度优先遍历:");
        List<String> dfsResults = new ArrayList<>();
        for (int i = 0; i < vertexs.length; i++) {
            if (!isVisited[i]) {
                DFS(isVisited, i, dfsResults);
            }
        }
        System.out.println(StringUtils.join(dfsResults, "->"));
    }

    private void DFS(boolean[] isVisited, int i, List<String> dfsResults) {
        dfsResults.add(getValue(i));
        isVisited[i] = true;
        int ajcVer = getFirstAjc(i);
        while (ajcVer != -1) {
            if (!isVisited[ajcVer]) {
                DFS(isVisited, ajcVer, dfsResults);
            }
            ajcVer = getNextAjc(i, ajcVer);
        }
    }

    /**
     * 广度优先遍历
     */
    public void BFS() {
        System.out.println("广度优先遍历:");
        List<String> bfsResults = new ArrayList<>();
        for (int i = 0; i < vertexs.length; i++) {
            if (!isVisited[i]) {
                BFS(isVisited, i, bfsResults);
            }
        }
        System.out.println(StringUtils.join(bfsResults, "->"));
    }

    private void BFS(boolean[] isVisited, int i, List<String> bfsResults) {
        // 队列头
        int h;
        // 邻接点
        int ajc;
        Queue<Integer> queue = new LinkedBlockingQueue<>();
        bfsResults.add(getValue(i));
        isVisited[i] = true;
        queue.offer(i);
        while (!queue.isEmpty()) {
            // 1.取队列头，未访问邻接点
            h = queue.poll();
            ajc = getNextNoAccessAjcVer(h);
            while (ajc != -1) {
                // 2.访问邻接点入队列
                if (!isVisited[ajc]) {
                    queue.offer(ajc);
                    bfsResults.add(getValue(ajc));
                    isVisited[ajc] = true;
                }
                // 3.下一个未访问邻接点
                ajc = getNextNoAccessAjcVer(h);
            }
        }
    }

    /**
     * 拓扑排序 (tops[]：拓扑结果，inDegres[]:入度数组，queue：辅助队列)
     * 1.入度0的点进队列
     * 2.队列头依次出h，对出队的点影响到的邻接点入度减1
     */
    public int topologicalSort() {
        // 拓扑结果
        String[] tops = new String[vertexs.length];
        // tops下标
        int index = 0;
        // 入度数组
        int[] inDegrees = new int[vertexs.length];
        // 辅助队列
        Queue<Integer> queue = new LinkedBlockingQueue<>();

        for (int i = 0; i < edges.length; ++i) {
            for (int j = 0; j < edges[i].length; ++j) {
                if (edges[i][j] > 0) {
                    // i->j, j入度 +1
                    inDegrees[j]++;
                }
            }
        }

        // 入度为0的入队列
        for (int i = 0; i < inDegrees.length; ++i) {
            if (inDegrees[i] == 0) {
                queue.offer(i);
            }
        }

        // 不断从队列头取出，并对邻接点入度减1
        while (!queue.isEmpty()) {
            int ver = queue.poll().intValue();
            tops[index++] = getValue(ver);
            for (int j = 0; j < edges.length; ++j) {
                if (edges[ver][j] > 0) {
                    // 入度减1
                    inDegrees[j]--;
                    if (inDegrees[j] == 0) {
                        queue.offer(j);
                    }
                }
            }
        }

        if (index < vertexs.length) {
            System.out.println("图中有环，不是DAG");
            return -1;
        }

        System.out.printf("拓扑排序:%s\n", Arrays.toString(tops));
        return 0;
    }

    /**
     * dijkstra算法最短路径（v：源点，st[]：S集合，确定点，dist[]：距离数组，v到下标的最短距离，pre[]：最短距离中到下标的前一点）
     * 1.找到未确定最短距离中最短的，加到S集合
     * 2.更新确定点i后，i对直接后续邻接点的距离影响，如最短距离变小，则更新
     *
     * @param v
     * @return
     */
    public int[] dijkstra(int v) {
        // 每个点i最短距离确定之后，i的前一个结点
        int[] pre = new int[vertexs.length];
        // 集合S
        boolean[] st = new boolean[vertexs.length];
        // 距离
        int[] dist = new int[vertexs.length];

        int[][] copyEdge = new int[edges.length][edges.length];
        for (int i = 0; i < edges.length; ++i) {
            copyEdge[i] = Arrays.copyOfRange(edges[i], 0, edges[i].length);
        }
        // 不嫩到达的距离为无穷
        for (int i = 0; i < copyEdge.length; ++i) {
            for (int j = 0; j < copyEdge[i].length; ++j) {
                if (i != j && copyEdge[i][j] == 0) {
                    copyEdge[i][j] = INF;
                }
            }
        }

        // 初始化
        st[v] = true;
        for (int i = 0; i < copyEdge.length; ++i) {
            dist[i] = copyEdge[v][i];
            pre[i] = v;
        }

        // 遍历找出最短距离
        for (int i = 0; i < dist.length; ++i) {
            int min = INF;
            int index = -1;
            // 1.找出未确定的点中的最短距离
            for (int j = 0; j < dist.length; ++j) {
                if (!st[j] && dist[j] < min) {
                    min = dist[j];
                    index = j;
                }
            }

            // 2.更新j影响到的最短距离
            if (index != -1) {
                st[index] = true;
                for (int n = 0; n < dist.length; ++n) {
                    if (!st[n] && (copyEdge[index][n] != INF) &&
                            (min + copyEdge[index][n]) < dist[n]) {
                        dist[n] = min + copyEdge[index][n];
                        pre[n] = index;
                    }
                }
            }
        }
        System.out.printf("最短距离(%d):%s\n", v, Arrays.toString(dist));
        System.out.printf("最短距离pre数组:%s\n", Arrays.toString(pre));
        return pre;
    }

    /**
     * 最短路径详细信息
     *
     * @param v1
     * @param v2
     * @param pre
     * @return
     */
    public String printMinDist(int v1, int v2, int[] pre) {
        Stack<Integer> stack = new Stack<>();
        List<String> list = new ArrayList<>();
        // 最短路径
        int dist = 0;
        stack.push(v2);
        while (v1 != v2) {
            v2 = pre[v2];
            stack.push(v2);
        }
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            dist = dist + ((stack.isEmpty()) ? 0 : getWeight(pop, stack.peek()));
            list.add(getValue(pop));
        }
        System.out.printf("最短路径结点：%s——最短路径:%d\n", String.join("->", list), dist);
        return String.join("->", list);
    }

    /**
     * 深度优先搜索最短路径
     *
     * @param v1
     * @param v2
     * @param temp
     */
    public int minDistDFS(int v1, int v2, int temp) {
        int min = INF;
        return minDistDFS(v1, v2, temp, min);
    }

    private int minDistDFS(int v1, int v2, int temp, int min) {
        // 从v1到达了v2 返回累加好的路径值
        if (v1 == v2) {
            if (temp < min) {
                min = temp;
            }
            return min;
        }

        // <v1,v2>，首先走v1 -> i，
        // 循环i，并递归（把i当做v1，此时<v1,v2>的路径就变为<v1,i>的确定路径加 <i,v2>的路径。<i,v2>的路径进行递归返回）
        // 每次遍历完i，对i的访问标记恢复为未访问，目的是for遍历i的下一个点能通过其他路径访问到达v2
        for (int i = 0; i < edges.length; ++i) {
            if (!isVisited[i] && edges[v1][i] > 0 && edges[v1][i] != min) {
                isVisited[i] = true;
                min = minDistDFS(i, v2, temp + edges[v1][i], min);
                isVisited[i] = false;
            }
        }
        return min;
    }

    /******************************************************************/
    public static void main(String[] args) {
        // 节点个数
        int n = 7;
        String[] vertexc = {"A", "B", "C", "D", "E", "F", "G"};
        DGraphMatrix dgMatrix = new DGraphMatrix(n);
        for (String s : vertexc) {
            dgMatrix.addVer(s);
        }

        // 添加边<A,B> <B,C> <C,D> <C,E> <A,F> <F,G> <G,C>
        dgMatrix.addEdge(0, 1, 10);
        dgMatrix.addEdge(1, 2, 20);
        dgMatrix.addEdge(2, 3, 30);
        dgMatrix.addEdge(2, 4, 4);
        dgMatrix.addEdge(0, 5, 1);
        dgMatrix.addEdge(5, 6, 2);
        dgMatrix.addEdge(6, 2, 3);

        dgMatrix.show();

        dgMatrix.DFS();
        dgMatrix.clearVisited();
        dgMatrix.BFS();
        dgMatrix.clearVisited();

        dgMatrix.topologicalSort();
        int[] pre = dgMatrix.dijkstra(0);
        dgMatrix.printMinDist(0, 4, pre);

        System.out.println(dgMatrix.minDistDFS(0, 4, 0));
    }
}














